package problems;

import java.util.HashMap;
import java.util.Map;

public class Euler014 extends AbstractEuler {

	private Map<Long, Integer> chainLength = new HashMap<Long, Integer>();
	{
		chainLength.put(1L, 0);
	}
	
	private int calculateLength(long n) {
		if (!chainLength.containsKey(n)) {
			if (n % 2 == 0) {
				chainLength.put(n, calculateLength(n/2) + 1);
			} else {
				chainLength.put(n, calculateLength(3*n + 1) + 1);
			}
		}
		
		return chainLength.get(n);
	}
	
	@Override
	public Number calculate() {
		int maxLength = 0;
		int keyWithMaxLength = 0;
		for (int i = 1; i < 1000000; i++) {
			int length = calculateLength(i);
			if (length > maxLength) {
				maxLength = length;
				keyWithMaxLength = i;
			}
		}
		return keyWithMaxLength;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 837799;
	}

}
